package LearnAlgorithm.h_标准数学公式;

/**
 * @version: 1.0
 * @Author: wuqiu
 * @date: 2023-07-17 22:21
 * @description: LeetcodeLearnAlgorithm -> LearnAlgorithm.h_标准数学公式
 */

import java.util.Arrays;
import java.util.HashMap;
import java.util.Random;

/**
 * k-Means算法，聚类算法；
 * 实现步骤：
 * 1. 首先是随机获取总体中的K个元素作为总体的K个中心；
 * 2. 接下来对总体中的元素进行分类，每个元素都去判断自己到K个中心的距离，并归类到最近距离中心去；
 * 3. 计算每个聚类的平均值，并作为新的中心点
 * 4. 重复2，3步骤，直到这k个中心点不再变化（收敛了），或执行了足够多的迭代
 */
public class l聚类算法KMeans {
    //k个中心点;在代码角度看，这个“点”是包含很多double的数组
    public int K;
    //记录每个元素的归属。对DATA的每个元素(元素指的是double[]数组)，都会有一个“归属”：即“距离”最近的的“中心点”；“距离”指的是“manhattanDistance()方法算出来的距离”
    public int[] memberShip;
    //记录每个中心点，在DATA中的索引，centersIndex的长度是K
    public int[] centersIndex;
    //最终返回的中心点的集合，用二维数组来充当集合容器
    public double[][] centers;
    //每个中心点聚合的元素个数。记录每个“中心点”A，有多少个归属于A的其他点，其他点的个数记录在这个数组中；所以数组长度为K，每个索引对应centersIndex[]数组的索引
    public int[] elementsInCenters;

    public l聚类算法KMeans(int k) {
        this.K = k;
    }

    /**
     * 计算曼哈顿距离
     *
     * @param paraFirstData
     * @param paraSecondData
     * @return
     */
    public double manhattanDistance(double[] paraFirstData, double[] paraSecondData) {
        double tempDistance = 0;
        //检查参数是否符合要求
        if ((paraFirstData != null && paraSecondData != null) && paraFirstData.length == paraSecondData.length) {
            //通过if判断，确定了两数组长度一致；进行两数组的每个元素的逐一操作
            for (int i = 0; i < paraFirstData.length; i++) {
                //取出同索引位置上的元素，相减，取绝对值，累加
                tempDistance += Math.abs(paraFirstData[i] - paraSecondData[i]);
            }
        } else {
            System.out.println("firstData 与 secondData 数据结构不一致");
        }
        //返回曼哈顿距离
        return tempDistance;
    }

    /**
     * 构造centersIndex[]
     * 随机选取K个中心点
     * K < DATA.length
     * 不用担心选取的中心点过多
     *
     * @param DATA
     */
    public void randomCenters(double[][] DATA) {
        //生成的中心点，在DATA中的坐标
        centersIndex = new int[K];
        //随机选取的帮助类之一
        Random random = new Random();
        //随机选取的帮助类之一
        HashMap<Integer, double[]> helper = new HashMap<Integer, double[]>();
        for (int i = 0; i < K; i++) {
            int current = Math.abs(random.nextInt()) % DATA.length;//current的范围是[0,DATA.length-1]
            if (helper.containsKey(current)) {
                /*
                如果current已经被选中过一次，当中心点
                那么就代表当前本次循环产生的随机数不合格
                需要重新生成随机数，进而重新生成中心点
                我们要回溯一次i
                 */
                i--;
            } else {
                //没被选中过，那就添加
                helper.put(current, DATA[current]);
                //将中心点的下标存入centerIndex[]中
                centersIndex[i] = current;//一共要选取出K个current；一般K是小于DATA.length的
            }
        }
    }

    /**
     * 构造memberShip[]和elementsInCenters[]
     * 对每个DATA元素element，与所有的中心点，逐一计算曼哈顿距离
     * 选出element视角下，记录最佳的距离，最佳的中心点(通过centersIndex[]的索引记录)到memberShip[]中
     * 把memberShip[]记录结果统计到elementsInCenters[]
     * @param DATA
     */
    public void calculateMemberShip(double[][] DATA) {
        //对DATA的每个元素(元素指的是double[]数组)，都会有一个“归属”：即“距离”最近的的“中心点”；“距离”指的是“manhattanDistance()方法算出来的距离”
        memberShip = new int[DATA.length];
        //记录每个“中心点”A，有多少个归属于A的其他点，其他点的个数记录在这个数组中；所以数组长度为K，每个索引对应centersIndex[]数组的索引
        elementsInCenters = new int[K];
        /*
        对每个DATA的元素遍历
         */
        for (int j = 0; j < DATA.length; j++) {
            //预先定义好“曼哈顿距离”和“归属的中心点的索引”
            double currentDistance = Double.MAX_VALUE;
            int currentCenterIndex = -1;
            //取出一个DATA元素element
            double[] element = DATA[j];
            //对每个中心点进行曼哈顿距离计算，选出距离最小的中心点
            for (int i = 0; i < K; i++) {
                //选出一个中心点索引centersIndex[i]，通过索引选出一个中心点DATA[centersIndex[i]]
                double[] tempCentersValue = DATA[centersIndex[i]];
                //计算曼哈顿距离
                double distance = manhattanDistance(element, tempCentersValue);
                //判断是否更新历史最佳距离和最佳索引
                if (distance < currentDistance) {
                    currentDistance = distance;
                    currentCenterIndex = i;
                }
            }
            //对当前的元素element,写上它的“归属”
            memberShip[j] = currentCenterIndex;
        }

        //对每个中心点，聚合多少个普通点，进行更新
        for (int i = 0; i < memberShip.length; i++) {
            /*
            当前DATA中，索引i处的element，的归属，在centersIndex[]中的索引A，是memberShip[i]
            那么，在elementsInCenters[]数组中，相同索引A处的，element进行++操作，代表这个中心点新加了一个“普通点”
             */
            elementsInCenters[memberShip[i]]++;
        }
    }

    /**
     * 构造double[][] 跳出循环时最终的中心点们的集合
     * @param DATA
     */
    public void calculateNewCenters(double[][] DATA) {
        //获取DATA的每个element的长度
        int elementLength = DATA[0].length;
        //创建跳出循环时最终的中心点们的集合,其中element的个数是K个，element的长度是elementLength
        centers = new double[K][elementLength];
        /*
        memberShip.length == 原DATA.length
        memberShip[i]的数值是[0,K-1],数值代表中心点在centersIndex的索引，不会造成越界
        这一步是“累加DATA数值到“跳出循环时最终的中心点们的集合”中的应该的位置”，即“每个聚类的数值累加”
         */
        for (int i = 0; i < memberShip.length; i++) {//memberShip.length == 原DATA.length
            for (int j = 0; j < elementLength; j++) {
                centers[memberShip[i]][j] += DATA[i][j];
            }
        }

        /*
        centers.length == K
        这一步就是求“每个聚类的平均值”，上一步已经累加完毕，这一步就是做除法
        除数是elementsInCenters[i]中的“每一个中心点聚合了多少个普通点”
         */
        for (int i = 0; i < centers.length; i++) {
            for (int j = 0; j < elementLength; j++) {
                centers[i][j] /= elementsInCenters[i];
            }
        }
        /*
        做完以后，“跳出循环时最终的中心点们的集合”算是生成完毕
         */
    }

    /**
     * 在聚合操作，结束以后。也就是K收敛了。这个方法展示所有曼哈顿距离的总和
     *
     * @param DATA
     * @return
     */
    public double computeTotalDistance(double[][] DATA) {
        double tempTotal = 0;
        //对每个DATA中的element，计算element到最佳中心点的曼哈顿距离，把这个距离进行累加，累加所有element的！
        for (int i = 0; i < DATA.length; i++) {
            tempTotal += manhattanDistance(DATA[i], centers[memberShip[i]]);
        }
        return tempTotal;
    }

    public void useKMeans(double[][] DATA) {
        String lastMemeberShip = "";
        String currentMemeberShip = "";
        int i = 0;
        while (i < 50000) {//人为规定最大聚合次数
            i++;

            randomCenters(DATA);
            System.out.println("随机选中的中心index为：" + Arrays.toString(centersIndex));

            calculateMemberShip(DATA);
            currentMemeberShip = Arrays.toString(memberShip);
            System.out.println("DATA聚类之后Membership为：" + currentMemeberShip);
            System.out.println("Elements in centers count is:" + Arrays.toString(elementsInCenters));

            if (currentMemeberShip.equals(lastMemeberShip)) {
                System.out.println("本次聚类与上次相同，退出执行！");
                System.out.println("一共聚类了 " + i + " 次！");
                calculateNewCenters(DATA);
                System.out.println("新中心点为：" + Arrays.deepToString(centers));
                double totalDistance = computeTotalDistance(DATA);
                System.out.println("totalDistance ： " + totalDistance);
                break;
            } else {
                lastMemeberShip = currentMemeberShip;
            }
            System.out.println("----------------这里是第" + i + "次聚合----------------");
        }
    }


    public static void main(String[] args) {
        l聚类算法KMeans test = new l聚类算法KMeans(5);
        double[][] DATA = {
                {5.1, 3.5, 1.4, 0.2},
                {4.9, 3.0, 1.4, 0.2},
                {4.6, 3.1, 1.5, 0.2},
                {7.0, 3.2, 4.7, 1.4},
                {6.9, 3.1, 4.9, 1.5},
                {6.5, 2.8, 4.6, 1.5},
                {6.5, 3.0, 5.8, 2.2},
                {4.9, 2.5, 4.5, 1.7},
                {6.7, 2.5, 5.8, 1.8},
                {4.7, 3.2, 1.3, 0.2},
                {5.0, 3.6, 1.4, 0.2},
                {6.4, 3.2, 4.5, 1.5},
                {5.5, 2.3, 4.0, 1.3},
                {5.7, 2.8, 4.5, 1.3},
                {7.6, 3.0, 6.6, 2.1},
                {7.3, 2.9, 6.3, 1.8},
                {6.9, 3.1, 5.1, 2.3}
        };
        test.useKMeans(DATA);
    }
}
